package com.bigshen.algorithm.kDFS.solution02Subsets;

import java.util.ArrayList;
import java.util.List;

/**
 * 78. Subsets 子集
 * Given an integer array nums, return all possible subsets (the power set).
 *
 * The solution set must not contain duplicate subsets.
 *
 *  
 *
 * Example 1:
 *
 * Input: nums = [1,2,3]
 * Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 * Example 2:
 *
 * Input: nums = [0]
 * Output: [[],[0]]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/subsets
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        if (null == nums || nums.length == 0) {
            return result;
        }

        // dfs:深度优先
        List<Integer> list = new ArrayList();
        dfs(result, nums, list, 0);

        // order，两层遍历
        // result.add(new ArrayList());
        // order(result, nums);

        return result;
    }

    // dfs: 1, 1-2, 1-2-3, 1-3, 2, 2-3, 3
    private void dfs(List<List<Integer>> result, int[] nums, List<Integer> list, int index) {
        result.add(new ArrayList(list));
        for (int i = index; i < nums.length; i ++) {
            list.add(nums[i]);
            dfs(result, nums, list, i+1);
            list.remove(list.size()-1);
        }
    }

    // 正向遍历，遇到一个数就把原有结果集中加入该数
    // [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]
    private void order(List<List<Integer>> result, int[] nums) {
        // 第一层遍历元素数组
        for (int i = 0; i < nums.length; i ++) {
            // 第二层遍历历史结果集
            int size = result.size();
            for (int j = 0; j < size; j ++) {
                List<Integer> clone = new ArrayList(result.get(j));
                clone.add(nums[i]);
                result.add(clone);
            }
        }
    }

}